Primzahl

Prim|zahl 〈f. 20〉 nur durch 1 u. durch sich selbst teilbare ganze Zahl [zu lat. primus „der erste“]

* * *

Prim|zahl, die; -, -en (Math.):

ganze Zahl, die größer als 1 u. nur durch 1 u. sich selbst teilbar ist.

* * *

I

Primzahl,

 

eine natürliche Zahl p, die größer als 1 ist und nur sich selbst und 1 als Teiler in der Menge der natürlichen Zahlen besitzt, z. B. 2, 3, 5, 7, 11, 13,. ..; eine Primzahl p > 1 teilt ein Produkt zweier natürlicher Zahlen nur dann, wenn p mindestens einen der beiden Faktoren teilt. Jede natürliche Zahl n > 1 lässt sich, bis auf die Reihenfolge der Faktoren, auf genau eine Weise als Produkt von Potenzen von voneinander verschiedenen Primzahlen schreiben (Primfaktorzerlegung).

 

Schon Euklid hat bewiesen, dass es unendlich viele Primzahlen gibt. Ein einfaches Verfahren, die Primzahlen unter den natürlichen Zahlen zu ermitteln, ist das Sieb des Eratosthenes. Die größte bis 2001 ermittelte Primzahl ist die mersennesche Primzahl 2^{13 466 917} — 1; sie hat in dezimaler Schreibweise rd. 4 Mio. Stellen. Das Bestimmen besonders großer Primzahlen ist nicht nur Ausdruck der hohen Rechenkapazität moderner Computer, sondern auch in der Kryptologie von besonderer Bedeutung. Jede Primzahl lässt sich in der Form p = 6k ± 1 (in der k natürliche Zahlen sind) darstellen, aber auch als Summe von höchstens vier Quadraten. Die Primzahlen der Form 2^k - 1 sind die mersenneschen Primzahlen (Mersenne-Zahlen), diejenigen der Form + 1 die fermatschen Primzahlen (fermatsche Zahlen). L. Euler hat gezeigt, dass die unendliche Reihe ∑ (1 / p) der Reziproken der Primzahlen divergiert. Da jedoch die unendliche Reihe ∑ (1 / n²) der Reziproken der Quadratzahlen konvergiert, müssen die Primzahlen insgesamt dichter liegen als die Quadratzahlen.

 

Die Verteilung der Primzahlen in der Folge aller natürlichen Zahlen ist sehr unregelmäßig: Einerseits gibt es zwischen zwei aufeinander folgenden Primzahlen beliebig große Lücken, z. B. ist keine der n — 1 aufeinander folgenden Zahlen n! + 2, n! + 3,. .., n! + n eine Primzahl, andererseits treten immer wieder Primzahlzwillinge auf. Man kann jedoch die Anzahl π (x) der Primzahlen kleiner oder gleich x asymptotisch immer genauer durch die Funktion x / ln x bestimmen (Primzahlsatz).

 

In jeder arithmetischen Folge (a, a + k, a + 2k, a + 3k...), für die a und k teilerfremd sind, gibt es nach P. G. Dirichlet (1837) unendlich viele Primzahlen. Schon 1742 stellte C. von Goldbach die Vermutungen auf, dass jede gerade natürliche Zahl N ≧ 6 die Summe zweier ungerader Primzahlen sei; die Richtigkeit dieser goldbachschen Vermutung ist bis heute noch nicht bewiesen. Eine Folgerung aus ihr ist es, dass jede ungerade natürliche Zahl n > 6 die Summe dreier ungerader Primzahlen sein müsste. Zu dieser Vermutung hat I. M. Winogradow 1937 die Existenz einer Zahl r bewiesen mit der Eigenschaft, dass sich zumindest jede ungerade natürliche Zahl n > r als Summe dreier Primzahlen darstellen lässt; es ist aber nur bekannt, dass r ≦ ist.

 

Literatur:

 

Lebendige Zahlen, bearb. v. W. Borho u. a. (Basel 1981);

 A. Weil: Zahlentheorie (a. d. Engl., Basel 1992);

 P. Ribenboim: The new book of prime number records (Neuausg. New York 1996).

II

Primzahl,

 

eine Zahl, die (ohne Rest) nur durch eins oder sich selbst teilbar ist. Mit Ausnahme der Zwei sind alle Primzahlen ungerade, die kleinsten sind 1, 2, 3, 5, 7, 11, 13, 17,. .. Es gibt unendlich viele Primzahlen, allerdings werden auch die Abstände zwischen aufeinander folgenden Zahlen immer größer. Um Primzahlen zu finden, wurden verschiedene Algorithmen erdacht, einer der schnellsten ist das Sieb des Eratosthenes. Das Auffinden sehr großer Primzahlen gehört zu den schwierigsten und rechenintensivsten Aufgaben in Mathematik und Informatik. Die fünf größten bekannten Primzahlen (Stand Januar 2002) wurden mit dem Rechennetzwerk GIMPS (Grid Computing) gefunden, die größte von ihnen ist die Zahl 2^13466917 - 1, die über vier Millionen Stellen besitzt.

 

Primzahlen spielen nicht nur in der Zahlentheorie, sondern auch in dem aktuellen Anwendungsgebiet der Datenverschlüsselung einer wichtige Rolle. Beispielsweise nutzt der RSA-Algorithmus (RSA-Verschlüsselung) die Tatsache aus, dass es zwar sehr einfach ist, zwei Primzahlen miteinander zu multiplizieren, es dagegen extrem schwierig ist, die (unbekannten) Primfaktoren einer großen Zahl zu finden. Da dieses Verschlüsselungsverfahren desto sicherer ist, je größere Primzahlen verwendet werden, liefert es eine Motivation zur Suche neuer Rekordprimzahlen.

 

* * *

Prim|zahl, die; -, -en (Math.): ganze Zahl, die größer als 1 u. nur durch 1 u. sich selbst teilbar ist.